
from typing import List

class Solution:

    def maximalSquare(self, matrix: List[List[str]]) -> int:
        n = len(matrix)
        m = len(matrix[0])
        dp = [[0 for _ in range(m)] for _ in range(n)]
        maxedge = 0
        for i in range(n):
            for j in range(m):
                if matrix[i][j] == '1':
                    if i == 0 or j == 0:
                        dp[i][j] = 1
                    else:
                        dp[i][j] = min([dp[i-1][j-1], dp[i-1][j], dp[i][j-1]]) + 1
                    if dp[i][j] > maxedge:
                        maxedge = dp[i][j]
        for e in matrix:
            print(e)
        print()
        for e in dp:
            print(e)
        return maxedge**2

if __name__ == "__main__":
    print("最大正方形: https://leetcode.cn/problems/maximal-square/submissions/543690063/\n")
    print("这个先用暴力法做了：对每个元素，以它为起点，右边增加列、下边增加行进行搜索，但是重复计算太多，超时\n")
    print("动态规划： 一开始没找到正确的状态转移方程，将dp[i][j]作为每个正方形的起始点。其实应该是终结点（正方形右下角）\n\n")
    test = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
    #test = [["1", "1"], ["1", "1"]]
    #test = [["0","0","0","1"],["1","1","0","1"],["1","1","1","1"],["0","1","1","1"],["0","1","1","1"]]
    test = [["0","1"],["1","0"]]
    ret = Solution().maximalSquare(test)
    print(ret)